Storage Discussion

A simple model of how data is stored

Let’s consider a customer record:

The underlying data becomes bit pattern that can be translated into an integer, say 64 bits or 8 bytes, and a string in Postgres that can be in theory of any length. How would we store this?

For simplicity’s sake we could say that, for now, a string could be up to an arbitrary 200 bytes, ignoring the complexities of UTF character encoding for the sake of this discussion.

This would give us a naive way of storing a customer record that would always take 8 bytes (for the integer) and 200 bytes for the string. We could then create a file that is sliced up into 208 byte chunks. This is similar to how data was stored in the old COBOL days, except that language didn’t use binary representations of numbers, but instead the concept of pictures that described how the number would be represented. Arithmetic was done in line and then written back to the format. These were simpler times and you could look at the files as raw data and work out what was in them.

If we are willing to live with this we could store the information for a customer. We might also add a marker record that says where the end of the active customer data is, so when we retrieve it we don’t search through a heap of empty records.

Updating our data

In this scheme updating data is relatively trivial:

1. Scan the customer file record by record until we find the ID we want
2. Replace what’s in the file at this point with our new data, as long as we have fixed length records this is trivially easy.

Deleting our data

This is harder, there are few things we could do:

1. Come up with an empty record marker (maybe ID being 0 )
2. Scan through the file until you find the ID of the row you want to delete, mark it as deleted.

Inserting data over time

Over time we may have a file that has several empty records, and not a lot of space left towards the end of it. So we can

• Logically split the file by adding a new one
• Shuffle all the data to the beginning of the file so we have more space
• Write insert code so that it goes looking for deleted records and replaces them with new ones
• This becomes much harder as soon as we start having records that can be any length, or new columns have been added to the table and we need to store them and maybe set up default values.

Searching for a particular record

A simple search that uses the ID.

• Naively we could read the file one record at a time until we find the record with the ID or hit the end of the file.
• If we didn’t shuffle records and knew how many were in the file we could do a Binary search this would allow us to take the integer value of the ID and then use it to work out where the record should be and then go see if it’s there. This means the records must have been inserted in the slot their ID maps to.
• We could use an index to let us find data wherever it appears.

What does an RDBMS give you?

After this discussion of a very simple way of storing data for a single table it becomes obvious that a database system is a very sophisticated piece of software.

• Create tables
• Change data in tables
• Create indexes
• Update indexes when table data is updated
• Store arbitrary data in tables and manage variable length strings and other data that can vary
• Add and drop columns
• Clear up and manage unused space
• Allow many concurrent connections